Stacks, Queues, and Deques

• Stacks
  • What is a Stack?
  • Implement a Stack!
• Queues
  • What is a Queue?
  • Implement a Queue!
• Deques
  • What is a Deque?
  • Implement a Deque!

Stacks

What is a Stack?

I’m reminded of those PEZ® candy dispensers with the cool little tops… lift the top back and out “pops” a piece of candy from a spring loaded container. When its empty, you “push” down another pack of candy. The last piece you push in is the first one to pop out. They never really tasted that good did they?

A stack is a collection of objects that are inserted and removed according to the last-in, first-out (LIFO) principle. The addition of new items and the removal of existing items always takes place at the same end. Therefore newer items are near the top, while older items are near the base.

Another example is a stack of books on a desk. To illustrate, find a bunch of old textbooks you never read and have for odd sentimental reasons. Place the books one by one on top of each other. Now start removing them. Notice the order that they are removed is exactly the reverse of the order that they were placed. Stacks can be used to reverse the order of items and a useful tool for many more sophisticated data structures and algorithms. Hey you learned something and those old college textbooks came in handy after all!

The stack abstract data type is defined by the following structure and operations. A stack is structured, as described above, as an ordered collection of items where items are added to and removed from the end called the “top.” Stacks are ordered LIFO. The stack operations are given below.

• Stack() creates a new stack that is empty. It needs no parameters and returns an empty stack.
• push(item) adds a new item to the top of the stack. It needs the item and returns nothing.
• pop() removes the top item from the stack. It needs no parameters and returns the item. The stack is modified.
• peek() returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.
• isEmpty() tests to see whether the stack is empty. It needs no parameters and returns a boolean value.
• size() returns the number of items on the stack. It needs no parameters and returns an integer.

For example, if s is a stack that has been created and starts out empty, then [Table 1][1] shows the results of a sequence of stack operations. Under stack contents, the top item is listed at the far right.

Table 1: Sample Stack Operations

Implement a Stack!

Now that we have clearly defined the stack as an abstract data type we will turn our attention to using Python to implement the stack. Recall that when we give an abstract data type a physical implementation we refer to the implementation as a data structure.

As we described in Chapter 1, in Python, as in any object-oriented programming language, the implementation of choice for an abstract data type such as a stack is the creation of a new class. The stack operations are implemented as methods. Further, to implement a stack, which is a collection of elements, it makes sense to utilize the power and simplicity of the primitive collections provided by Python. We will use a list.

Recall that the list class in Python provides an ordered collection mechanism and a set of methods. For example, if we have the list [2,5,3,6,7,4], we need only to decide which end of the list will be considered the top of the stack and which will be the base. Once that decision is made, the operations can be implemented using the list methods such as append and pop.

Let’s start coding! Create a stack class in Python below using a list and the append(), pop() methods.

It is important to note that we could have chosen to implement the stack using a list where the top is at the beginning instead of at the end. In this case, the previous pop and append methods would no longer work and we would have to index position 0 (the first item in the list) explicitly using pop and insert. The implementation is shown in []

This ability to change the physical implementation of an abstract data type while maintaining the logical characteristics is an example of abstraction at work. However, even though the stack will work either way, if we consider the performance of the two implementations, there is definitely a difference. Recall that the append and pop() operations were both O(1). This means that the first implementation will perform push and pop in constant time no matter how many items are on the stack. The performance of the second implementation suffers in that the insert(0) and pop(0) operations will both require O(n) for a stack of size n. Clearly, even though the implementations are logically equivalent, they would have very different timings when performing benchmark testing.

Big O analysis:

Table 1.1 shows the running times for our Stack methods. The implementations for peek, isEmpty, and size use constant time O(1). A call to push or pop uses constant time O(1).

The space usage for a stack is O(n).

Queues

What is a Queue?

A queue is an ordered collection of items where the addition of new items happens at one end, called the “rear,” and the removal of existing items occurs at the other end, commonly called the “front.” As an element enters the queue it starts at the rear and makes its way toward the front, waiting until that time when it is the next element to be removed.

The most recently added item in the queue must wait at the end of the collection. The item that has been in the collection the longest is at the front. This ordering principle is sometimes called FIFO, first-in first-out. It is also known as “first-come first-served.”

Figure 1: A Queue of Python Data Objects

The simplest example of a queue is the typical line that we all participate in from time to time. We wait in a line for a movie, we wait in the check-out line at a grocery store, and we wait in the cafeteria line (so that we can pop the tray stack). Well-behaved lines, or queues, are very restrictive in that they have only one way in and only one way out. There is no jumping in the middle and no leaving before you have waited the necessary amount of time to get to the front.

Computer science also has common examples of queues. Our computer laboratory has 30 computers networked with a single printer. When students want to print, their print tasks “get in line” with all the other printing tasks that are waiting. The first task in is the next to be completed. If you are last in line, you must wait for all the other tasks to print ahead of you. We will explore this interesting example in more detail later.

In addition to printing queues, operating systems use a number of different queues to control processes within a computer. The scheduling of what gets done next is typically based on a queuing algorithm that tries to execute programs as quickly as possible and serve as many users as it can. Also, as we type, sometimes keystrokes get ahead of the characters that appear on the screen. This is due to the computer doing other work at that moment. The keystrokes are being placed in a queue-like buffer so that they can eventually be displayed on the screen in the proper order.

The queue abstract data type is defined by the following structure and operations. A queue is structured, as described above, as an ordered collection of items which are added at one end, called the “rear,” and removed from the other end, called the “front.” Queues maintain a FIFO ordering property. The queue operations are given below.

• Queue() creates a new queue that is empty. It needs no parameters and returns an empty queue.
• enqueue(item) adds a new item to the rear of the queue. It needs the item and returns nothing.
• dequeue() removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.
• isEmpty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.
• size() returns the number of items in the queue. It needs no parameters and returns an integer.

As an example, if we assume that q is a queue that has been created and is currently empty, then [Table 1][1] shows the results of a sequence of queue operations. The queue contents are shown such that the front is on the right. 4 was the first item enqueued so it is the first item returned by dequeue.

Table 1: Example Queue Operations

Implement a Queue!

It is again appropriate to create a new class for the implementation of the abstract data type queue. As before, we will use the power and simplicity of the list collection to build the internal representation of the queue.

We need to decide which end of the list to use as the rear and which to use as the front. The implementation shown in [Listing 1][1] assumes that the rear is at position 0 in the list. This allows us to use the insert function on lists to add new elements to the rear of the queue. The pop operation can be used to remove the front element (the last element of the list). Recall that this also means that enqueue will be O(n) and dequeue will be O(1).

Deques

What is a Deque?

A deque, also known as a double-ended queue, is an ordered collection of items similar to the queue. It has two ends, a front and a rear, and the items remain positioned in the collection. New items can be added at either the front or the rear. Likewise, existing items can be removed from either end.

In a sense, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.

It is important to note that even though the deque can assume many of the characteristics of stacks and queues, it does not require the LIFO and FIFO orderings that are enforced by those data structures. It is up to you to make consistent use of the addition and removal operations.

Figure 1: A Deque of Python Data Objects

Implement a Deque!

The deque abstract data type is defined by the following structure and operations. A deque is structured, as described above, as an ordered collection of items where items are added and removed from either end, either front or rear. The deque operations are given below.

• Deque() creates a new deque that is empty. It needs no parameters and returns an empty deque.
• addFront(item) adds a new item to the front of the deque. It needs the item and returns nothing.
• addRear(item) adds a new item to the rear of the deque. It needs the item and returns nothing.
• removeFront() removes the front item from the deque. It needs no parameters and returns the item. The deque is modified.
• removeRear() removes the rear item from the deque. It needs no parameters and returns the item. The deque is modified.
• isEmpty() tests to see whether the deque is empty. It needs no parameters and returns a boolean value.
• size() returns the number of items in the deque. It needs no parameters and returns an integer.

As an example, if we assume that d is a deque that has been created and is currently empty, then Table {dequeoperations} shows the results of a sequence of deque operations. Note that the contents in front are listed on the right. It is very important to keep track of the front and the rear as you move items in and out of the collection as things can get a bit confusing.

Table 1: Examples of Deque Operations

As we have done in previous sections, we will create a new class for the implementation of the abstract data type deque. Again, the Python list will provide a very nice set of methods upon which to build the details of the deque. Our implementation ([Listing 1][1]) will assume that the rear of the deque is at position 0 in the list.

In removeFront we use the pop method to remove the last element from the list. However, in removeRear, the pop(0) method must remove the first element of the list. Likewise, we need to use the insert method (line 12) in addRear since the append method assumes the addition of a new element to the end of the list.

You can see many similarities to Python code already described for stacks and queues. You are also likely to observe that in this implementation adding and removing items from the front is O(1) whereas adding and removing from the rear is O(n). This is to be expected given the common operations that appear for adding and removing items. Again, the important thing is to be certain that we know where the front and rear are assigned in the implementation.