Conceptual Theory of Queues and Stacks

_{Image credits to tensator}

Queues Introduction

A queue is a data structure which contains an ordered set of data.

Queues provide three methods for interaction:

• Enqueue - adds data to the “back” or end of the queue
• Dequeue - provides and removes data from the “front” or beginning of the queue
• Peek - reveals data from the “front” of the queue without removing it

This data structure mimics a physical queue of objects like a line of people buying movie tickets. Each person has a name (the data). The first person to enqueue, or get into line, is both at the front and back of the line. As each new person enqueues, they become the new back of the line.

When the cashier serves someone, they begin at the front of the line (or people would get very mad!). Each person served is dequeued from the front of the line, they purchase a ticket and leave.

If they just want to know who is next in line, they can peek and get their name without removing them from the queue.

The first person in the queue is the first to be served. Queues are a First In, First Out or FIFO structure.

_{Image credits to pleelaprasad @ Medium}

Queues Implementation

Queues can be implemented using a linked list as the underlying data structure. The front of the queue is equivalent to the head node of a linked list and the back of the queue is equivalent to the tail node.

Since operations are only allowed affecting the front or back of the queue, any traversal or modification to other nodes within the linked list is disallowed. Since both ends of the queue must be accessible, a reference to both the head node and the tail node must be maintained.

One last constraint that may be placed on a queue is its length. If a queue has a limit on the amount of data that can be placed into it, it is considered a bounded queue.

Similar to stacks, attempting to enqueue data onto an already full queue will result in a queue overflow. If you attempt to dequeue data from an empty queue, it will result in a queue underflow.

Queues Review

Let’s take a minute to review what we’ve covered about queues in this lesson.

Queues:

• Contain data nodes
• Support three main operations:
  • Enqueue adds data to the back of the queue
  • Dequeue removes and provides data from the front of the queue
  • Peek provides data on the front of the queue
• Can be implemented using a linked list or array
• Bounded queues have a limited size.
• Enqueueing onto a full queue causes a queue overflow
• Queues process data First In, First Out (FIFO)

Stacks Introduction

A stack is a data structure which contains an ordered set of data.

Stacks provide three methods for interaction:

• Push - adds data to the “top” of the stack
• Pop - returns and removes data from the “top” of the stack
• Peek - returns data from the “top” of the stack without removing it

Stacks mimic a physical “stack” of objects. Consider a set of gym weights.

Each plate has a weight (the data). The first plate you add, or push, onto the floor is both the bottom and top of the stack. Each weight added becomes the new top of the stack.

At any point, the only weight you can remove, or pop, from the stack is the top one. You can peek and read the top weight without removing it from the stack.

The last plate that you put down becomes the first, and only, one that you can access. This is a Last In, First Out or LIFO structure. A less frequently used term is First In, Last Out, or FILO.

Stacks Implementation

Stacks can be implemented using a linked list as the underlying data structure because it’s more efficient than a list or array.

Depending on the implementation, the top of the stack is equivalent to the head node of a linked list and the bottom of the stack is equivalent to the tail node.

A constraint that may be placed on a stack is its size. This is done to limit and quantify the resources the data structure will take up when it is “full”.

Attempting to push data onto an already full stack will result in a stack overflow. Similarly, if you attempt to pop data from an empty stack, it will result in a stack underflow.

_{Image credits to java2blog}

Stacks Review

Let’s take a minute to review what we’ve covered about stacks in this lesson.

Stacks:

• Contain data nodes
• Support three main operations
• Push adds data to the top of the stack
  • Pop removes and provides data from the top of the stack
  • Peek reveals data on the top of the stack
  • Implementations include a linked list or array
• Can have a limited size
  • Pushing data onto a full stack results in a stack overflow
• Stacks process data Last In, First Out (LIFO)