Stacks and Queues: Data Structures and Implementations
The activation record for the invoked function contains only a pointer to the previous stack frame and a return address. The previous stack frame pointer points to the stack frame of the invoking function, while the return address contains the location of the statement to be executed after the function terminates. Since only one function executes at any given time, the function whose stack frame is on top of the system stack is chosen. If this function invokes another function, the local variables, except those declared static, and the parameters of the invoking function are added to its stack frame. A new stack frame is then created for the invoked function and placed on top of the system stack. When this function terminates, its stack frame is removed and the processing of the invoking function, which is again on top of the stack, continues. A simple example illustrates this process. (We refer the reader who wants a more detailed discussion of stack frames to Holub’s book on compiler design cited in the References and Selected Readings section.) Assume that we have a main function that invokes function al. Figure 3.2(a) shows the system stack before al is invoked; Figure 3.2(b) shows the system stack after al has been invoked. Frame pointer fp is a pointer to the current stack frame. The system also maintains separately a stack pointer, sp, which we have not illustrated. Since all functions are stored similarly in the system stack, it makes no difference if the invoking function calls itself. That is, a recursive call requires no special strategy; the run-time program simply creates a new stack frame for each recursive call. However, recursion can consume a significant portion of the memory allocated to the system stack; it could consume the entire available memory. □ Our discussion of the system stack suggests several operations that we include in the ADT specification (Structure 3.1). The easiest way to implement this ADT is by using a one-dimensional array, say, stack[MAX-STACK-SIZE], where MAX_STACK_SIZE is the maximum number of entries. The first, or bottom, element of the stack is stored in stack[0], the second in stack[1], and the zth in stack[z-1]. Associated with the array is a variable, top, which points to the top element in the stack. Initially, top is set to -1 to denote an empty stack.
Queues are frequently used in computer programming, and a typical example is the creation of a job queue by an operating system. If the operating system does not use priorities, then the jobs are processed in the order they enter the system. Figure 3.5 illustrates how an operating system might process jobs if it used a sequential representation for its queue.
It should be obvious that as jobs enter and leave the system, the queue gradually shifts to the right. This means that eventually the rear index equals MAX_QUEUE_SIZE - 1, suggesting that the queue is full. In this case, queue_full should move the entire queue to the left so that the first element is again at queue[0] and front is at -1. It should also recalculate rear so that it is correctly positioned. Shifting an array is very time-consuming, particularly when there are many elements in it. In fact, queue_full has a worst-case complexity of O(MAX_QUEUE_SIZE). □ We can obtain a more efficient queue representation if we regard the array queue[MAX_QUEUE_SIZE] as circular. In this representation, we initialize front and rear to 0 rather than -1. The front index always points one position counterclockwise from the first element in the queue. The rear index points to the current end of the queue. The queue is empty if front == rear. Figure 3.6 shows empty and nonempty circular queues for MAX_QUEUE_SIZE = 6. Figure 3.7 illustrates two full queues for MAX_QUEUE_SIZE = 6. While these have space for one more element, the addition of such an element will result in front == rear and we won’t be able to distinguish between an empty and a full queue. So, we adopt the convention that a circular queue of size MAX_QUEUE_SIZE will be permitted to hold at most MAX_QUEUE_SIZE - 1 elements.
Implementing addq and deleteq for a circular queue is slightly more difficult since we must assure that a circular rotation occurs. This is attained by using the modulus operator. The circular rotation of the rear index in addq (Program 3.5) occurs in the statement: *rear = (*rear + 1) % MAX_QUEUE_SIZE; Notice that we rotate rear before we place the item in queue[rear]. Similarly, in deleteq (Program 3.6), we rotate front with the statement: *front = (*front + 1) % MAX_QUEUE_SIZE;
A circular queue is an extended version of a normal queue where the last element of the queue is connected to the first element of the queue forming a circle.
