Stacks and Queues

📖Guides
👤
- Kapil Vaishnav
⭐
Beginner Level
🏷️
- 150 DSA
📅06 August 2023

Stacks and queues are two fundamental data structures in computer science used to organize and manipulate data.

🌟 Stacks

A stack is an ordered collection of elements where the addition and removal of elements follow the "last-in, first-out" (LIFO) principle.
It resembles a stack of items, where the last item placed is the first one to be removed.
Elements can only be added or removed from the top of the stack.
Common operations on a stack include:
- Push: Adds an element to the top of the stack.
- Pop: Removes and returns the top element of the stack.
- Peek: Returns the top element of the stack without removing it.
Stacks are used in various scenarios, such as:
- Function call stack: Keeps track of function calls and their execution context.
- Expression evaluation: Evaluating arithmetic expressions using postfix notation.
- Undo/Redo functionality: Storing a sequence of actions to enable undoing or redoing.
- Browser history: Tracking the visited pages in a web browser.

🌟 Queues

A queue is an ordered collection of elements where the addition of elements follows the "first-in, first-out" (FIFO) principle.
It resembles a queue of people waiting in line, where the person who joins first is the first to be served.
Elements can only be added at the rear (enqueue) and removed from the front (dequeue) of the queue.
Common operations on a queue include:
- Enqueue: Adds an element to the rear of the queue.
- Dequeue: Removes and returns the front element of the queue.
- Peek: Returns the front element of the queue without removing it.
Queues are used in various scenarios, such as:
- Process scheduling: Managing tasks in an operating system, where the first task in is the next to be executed.
- Print spooling: Managing print jobs in a queue for a printer.
- Message queues: Handling inter-process communication in distributed systems.
- Breadth-first search: Traversing graphs level by level.

NOTE : Both stacks and queues are abstract data types that can be implemented using arrays or linked lists. There are also specialized variations of these structures, such as priority queues and double-ended queues (deques), which provide additional functionalities based on specific requirements.

🌟 Here are the operations for stacks and queues in C++ along with comments explaining each operation:

⏩ Stack Operations:

cpp Code Snippet

#include <stack>

int main() {
  std::stack<int> myStack; // Create an empty stack of integers
    
  myStack.push(10); // Push element 10 onto the stack
  myStack.push(20); // Push element 20 onto the stack
  myStack.push(30); // Push element 30 onto the stack

  int topElement = myStack.top(); // Access the top element of the stack (30)
  myStack.pop(); // Remove the top element from the stack (30)

  bool isEmpty = myStack.empty(); // Check if the stack is empty (false)
  int stackSize = myStack.size(); // Get the size of the stack (2)

return 0;
}
        

⏩ Queues Operations:

cpp Code Snippet

          #include <queue>

          int main() {
              std::queue<int> myQueue; // Create an empty queue of integers
          
              myQueue.push(10); // Enqueue element 10 into the queue
              myQueue.push(20); // Enqueue element 20 into the queue
              myQueue.push(30); // Enqueue element 30 into the queue
          
              int frontElement = myQueue.front(); // Access the front element of the queue (10)
              myQueue.pop(); // Dequeue/remove the front element from the queue (10)
          
              bool isEmpty = myQueue.empty(); // Check if the queue is empty (false)
              int queueSize = myQueue.size(); // Get the size of the queue (2)
          
              return 0;
          }
        

Note: Make sure to include the relevant header file <stack> for stacks and <queue> for queues before using these operations in your C++ program.

The statement unlike an array, a stack does not offer constant-time access to the ith item means that in a stack, you cannot directly access or retrieve an element at a specific position (ith index) like you can in an array. In a stack, you can only access the topmost element.

Example

cpp Code Snippet

        #include <iostream>
        #include <stack>
        
        int main() {
            std::stack<int> myStack;
        
            myStack.push(10); // Push element 10 onto the stack
            myStack.push(20); // Push element 20 onto the stack
            myStack.push(30); // Push element 30 onto the stack
        
            int element = myStack.top(); // Access the topmost element (30)
            std::cout << "Topmost element: " << element << std::endl;
        
            // Try accessing an element at a specific position (ith index)
            // This will not work because stacks do not provide direct access to elements
            // int secondElement = myStack[1]; // This will result in a compilation error
        
            return 0;
        }
        

However, if we try to access an element at a specific position (ith index) like myStack[1], it will result in a compilation error because stacks do not provide direct access to elements by index. Stacks are designed to allow constant-time adds and removes from the top, but not random access to elements in the middle or at specific positions.

In the above example, we create a stack myStack and push three elements onto it (10, 20, and 30). We can access the topmost element using the top() function, which gives us direct access to the element at the top of the stack (30 in this case).

Let's explain the second point: it does allow constant-time adds and removes, as it doesn't require shifting elements around.

In a stack, elements are added and removed from only one end, called the top of the stack. When you add an element, it is placed on top of the stack, and when you remove an element, you remove the topmost element.

This characteristic of stacks allows for constant-time adds and removes. It means that regardless of the number of elements in the stack, adding or removing an element takes the same amount of time, as the operation is always performed at the top of the stack.

This characteristic of stacks allows for constant-time adds and removes. It means that regardless of the number of elements in the stack, adding or removing an element takes the same amount of time, as the operation is always performed at the top of the stack.

Example:

cpp Code Snippet

        #include <iostream>
        #include <stack>
        
        int main() {
            std::stack<int> myStack;
        
            myStack.push(10); // Add element 10 to the top of the stack
            myStack.push(20); // Add element 20 to the top of the stack
            myStack.push(30); // Add element 30 to the top of the stack
        
            int topElement = myStack.top(); // Access the topmost element (30)
            std::cout << "Topmost element: " << topElement << std::endl;
        
            myStack.pop(); // Remove the topmost element (30)
            int newTopElement = myStack.top(); // Access the new topmost element (20)
            std::cout << "New topmost element: " << newTopElement << std::endl;
        
            return 0;
        }
        

In the above example, we create a stack myStack and add three elements to it (10, 20, and 30). When we push elements onto the stack, they are added to the top of the stack. The top() function allows us to access the topmost element directly, which in this case is 30.
When we perform a remove operation using the pop() function, it removes the topmost element from the stack. In this case, 30 is removed. After the removal, we can use the top() function again to access the new topmost element, which is 20.

The important point to note here is that adding and removing elements from the stack is a constant-time operation because it doesn't require shifting or rearranging the elements in the stack. It simply adds or removes an element from the top, making it an efficient and constant-time process.

🌟 What is constant Time?

Constant Time

In computer science, a constant-time operation refers to an operation that takes the same amount of time to execute, regardless of the size of the input or the data structure. The time taken by a constant-time operation remains constant, or in other words, it does not depend on the number of elements or the size of the data structure being operated upon.
In the context of the previous explanation about stacks, when we say that adding and removing elements from a stack is a constant - time operation, it means that regardless of the number of elements in the stack, the time it takes to add or remove an element remains the same.It does not increase as the stack grows larger.
For example, adding an element to the top of a stack using the push() operation or removing an element from the top using the pop() operation both take the same amount of time, regardless of the number of elements in the stack.
Constant - time operations are desirable because they offer predictable and efficient performance, making them highly efficient for data structures and algorithms. They are typically preferred over operations that have a time complexity that grows with the size of the input.
It is worth noting that not all operations in computer science are constant-time operations. Some operations have a time complexity that varies with the size of the input, such as linear time (O(n)), logarithmic time (O(log n)), or quadratic time (O(n^2)). Constant-time operations are considered the most efficient because their execution time remains constant, providing a predictable and consistent performance regardless of the input size.
In computer science, constant time complexity is represented as O(1), where "O" stands for "order of" or "big O" notation. The number 1 inside the parentheses indicates that the time complexity of the algorithm or operation is constant, meaning it does not depend on the input size.
The notation O(1) signifies that the time taken to perform an operation remains constant, regardless of the input size. It implies that the algorithm or operation has a fixed runtime, and the execution time does not increase as the input size grows.
For example, if you have an algorithm that performs a single operation on an array, such as accessing an element by its index or pushing an element onto a stack, and this operation takes the same amount of time regardless of the size of the array, then the time complexity of that operation is O(1).
Constant time complexity is considered the most efficient time complexity because the execution time remains constant, providing a predictable and consistent performance regardless of the input size.

Here's an example of implementing a stack and a queue in C++ using all the common methods:

cpp Code Snippet

        #include <iostream>
        #include <stack>
        #include <queue>
        
        int main() {
            // Stack implementation
            std::stack<int> myStack;
        
            // Push elements onto the stack
            myStack.push(10);
            myStack.push(20);
            myStack.push(30);
        
            // Check if the stack is empty
            if (myStack.empty()) {
                std::cout << "Stack is empty" << std::endl;
            } else {
                std::cout << "Stack is not empty" << std::endl;
            }
        
            // Access the top element of the stack
            std::cout << "Top element of the stack: " << myStack.top() << std::endl;
        
            // Pop elements from the stack
            myStack.pop();
        
            // Size of the stack
            std::cout << "Size of the stack: " << myStack.size() << std::endl;
        
            std::cout << std::endl;
        
            // Queue implementation
            std::queue<int> myQueue;
        
            // Push elements into the queue
            myQueue.push(10);
            myQueue.push(20);
            myQueue.push(30);
        
            // Check if the queue is empty
            if (myQueue.empty()) {
                std::cout << "Queue is empty" << std::endl;
            } else {
                std::cout << "Queue is not empty" << std::endl;
            }
        
            // Access the front and back elements of the queue
            std::cout << "Front element of the queue: " << myQueue.front() << std::endl;
            std::cout << "Back element of the queue: " << myQueue.back() << std::endl;
        
            // Pop elements from the queue
            myQueue.pop();
        
            // Size of the queue
            std::cout << "Size of the queue: " << myQueue.size() << std::endl;
        
            return 0;
        }
        

This code demonstrates the basic operations for both a stack and a queue. It includes pushing elements onto the stack/queue, checking if it's empty, accessing the top/front/back elements, popping elements, and getting the size of the stack/queue.

Here's the revised code with comments explaining each class and significant sections:

cpp Code Snippet

        #include <iostream>

        const int MAX_SIZE = 100;
        
        // Stack class using an array
        class Stack {
        private:
            int arr[MAX_SIZE]; // Array to store stack elements
            int top; // Index of the top element
        
        public:
            Stack() {
                top = -1; // Initialize top index to -1 (empty stack)
            }
        
            bool isEmpty() {
                return top == -1; // Check if the stack is empty
            }
        
            bool isFull() {
                return top == MAX_SIZE - 1; // Check if the stack is full
            }
        
            void push(int item) {
                if (isFull()) {
                    std::cout << "Stack Overflow!" << std::endl; // Stack is full, cannot push
                    return;
                }
                arr[++top] = item; // Increment top and add item to the top of the stack
                std::cout << "Pushed element: " << item << std::endl;
            }
        
            int pop() {
                if (isEmpty()) {
                    std::cout << "Stack Underflow!" << std::endl; // Stack is empty, cannot pop
                    return -1;
                }
                int item = arr[top--]; // Get the item at the top and decrement top
                std::cout << "Popped element: " << item << std::endl;
                return item;
            }
        
            int peek() {
                if (isEmpty()) {
                    std::cout << "Stack is empty!" << std::endl;
                    return -1;
                }
                return arr[top]; // Return the item at the top without removing it
            }
        };
        
        // Queue class using linked list
        class Node {
        public:
            int data;
            Node* next;
        
            Node(int value) {
                data = value;
                next = nullptr;
            }
        };
        
        class Queue {
        private:
            Node* front; // Pointer to the front of the queue
            Node* rear; // Pointer to the rear of the queue
        
        public:
            Queue() {
                front = nullptr; // Initialize front and rear pointers to nullptr (empty queue)
                rear = nullptr;
            }
        
            bool isEmpty() {
                return front == nullptr; // Check if the queue is empty
            }
        
            void enqueue(int item) {
                Node* newNode = new Node(item); // Create a new node
        
                if (isEmpty()) {
                    front = rear = newNode; // If the queue is empty, make the new node the front and rear
                } else {
                    rear->next = newNode; // Add the new node to the end of the queue
                    rear = newNode; // Update the rear pointer
                }
                std::cout << "Enqueued element: " << item << std::endl;
            }
        
            int dequeue() {
                if (isEmpty()) {
                    std::cout << "Queue is empty!" << std::endl; // Queue is empty, cannot dequeue
                    return -1;
                }
                Node* temp = front; // Temporarily store the front node
                int item = temp->data; // Get the item at the front
                front = front->next; // Move the front pointer to the next node
                delete temp; // Free memory of the previous front node
                std::cout << "Dequeued element: " << item << std::endl;
                return item;
            }
        
            int peek() {
                if (isEmpty()) {
                    std::cout << "Queue is empty!" << std::endl;
                    return -1;
                }
                return front->data; // Return the item at the front without removing it
            }
        
        
        };
        
        int main() {
            // Stack operations
            Stack stack;
            stack.push(10);
            stack.push(20);
            stack.push(30);
            stack.pop();
            stack.push(40);
            std::cout << "Top element of stack: " << stack.peek() << std::endl;
        
            std::cout << std::endl;
        
            // Queue operations
            Queue queue;
            queue.enqueue(10);
            queue.enqueue(20);
            queue.dequeue();
            queue.enqueue(30);
            std::cout << "Front element of queue: " << queue.peek() << std::endl;
        
            return 0;
        }
        

Here's the code implementing the Stack using a linked list and the Queue using an array with comments explaining each section:

cpp Code Snippet

          #include <iostream>

          // Node class for Stack
          class Node {
          public:
              int data; // Data of the node
              Node* next; // Pointer to the next node
          
              Node(int value) {
                  data = value;
                  next = nullptr;
              }
          };
          
          // Stack class using linked list
          class Stack {
          private:
              Node* top; // Pointer to the top of the stack
          
          public:
              Stack() {
                  top = nullptr; // Initialize top pointer to nullptr (empty stack)
              }
          
              bool isEmpty() {
                  return top == nullptr; // Check if the stack is empty
              }
          
              void push(int item) {
                  Node* newNode = new Node(item); // Create a new node
                  newNode->next = top; // Set the next pointer of the new node to the current top
                  top = newNode; // Update the top pointer to the new node
                  std::cout << "Pushed element: " << item << std::endl;
              }
          
              int pop() {
                  if (isEmpty()) {
                      std::cout << "Stack Underflow!" << std::endl; // Stack is empty, cannot pop
                      return -1;
                  }
                  Node* temp = top; // Temporarily store the top node
                  int item = temp->data; // Get the item at the top
                  top = top->next; // Move the top pointer to the next node
                  delete temp; // Free memory of the previous top node
                  std::cout << "Popped element: " << item << std::endl;
                  return item;
              }
          
              int peek() {
                  if (isEmpty()) {
                      std::cout << "Stack is empty!" << std::endl;
                      return -1;
                  }
                  return top->data; // Return the item at the top without removing it
              }
          };
          
          const int MAX_SIZE = 100;
          
          // Queue class using an array
          class Queue {
          private:
              int arr[MAX_SIZE]; // Array to store queue elements
              int front; // Index of the front element
              int rear; // Index of the rear element
          
          public:
              Queue() {
                  front = -1; // Initialize front and rear indices to -1 (empty queue)
                  rear = -1;
              }
          
              bool isEmpty() {
                  return front == -1; // Check if the queue is empty
              }
          
              bool isFull() {
                  return (rear + 1) % MAX_SIZE == front; // Check if the queue is full
              }
          
              void enqueue(int item) {
                  if (isFull()) {
                      std::cout << "Queue Overflow!" << std::endl; // Queue is full, cannot enqueue
                      return;
                  }
                  if (isEmpty()) {
                      front = rear = 0; // If the queue is empty, set front and rear indices to 0
                  } else {
                      rear = (rear + 1) % MAX_SIZE; // Increment the rear index circularly
                  }
                  arr[rear] = item; // Add the item to the rear of the queue
                  std::cout << "Enqueued element: " << item << std::endl;
              }
          
              int dequeue() {
                  if (isEmpty()) {
                      std::cout << "Queue Underflow!" << std::endl; // Queue is empty, cannot dequeue
                      return -1;
                  }
                  int item = arr[front]; // Get the item at the front
                  if (front == rear) {
                      front = rear = -1; // If the queue has only
          
           one element, reset front and rear indices
                  } else {
                      front = (front + 1) % MAX_SIZE; // Increment the front index circularly
                  }
                  std::cout << "Dequeued element: " << item << std::endl;
                  return item;
              }
          
              int peek() {
                  if (isEmpty()) {
                      std::cout << "Queue is empty!" << std::endl;
                      return -1;
                  }
                  return arr[front]; // Return the item at the front without removing it
              }
          };
          
          int main() {
              // Stack operations using linked list
              Stack stack;
              stack.push(10);
              stack.push(20);
              stack.push(30);
              stack.pop();
              stack.push(40);
              std::cout << "Top element of stack: " << stack.peek() << std::endl;
          
              std::cout << std::endl;
          
              // Queue operations using array
              Queue queue;
              queue.enqueue(10);
              queue.enqueue(20);
              queue.dequeue();
              queue.enqueue(30);
              std::cout << "Front element of queue: " << queue.peek() << std::endl;
          
              return 0;
          }
        

There are several ways to implement a stack using other data structures. Here are a few common approaches:

Array: In this approach, you can use a dynamic array and keep track of the index of the top element. The stack operations can be implemented by manipulating the index and accessing elements at specific indices in the array.
Linked List: You can implement a stack using a singly linked list. Each node in the linked list will represent an element in the stack, and the top of the stack will be represented by the head of the linked list. The stack operations can be implemented by manipulating the head pointer and adding/removing nodes at the beginning of the linked list.
Dynamic Array: Similar to the array approach, you can use a dynamically resizable array (such as std::vector in C++) to implement a stack. The stack operations can be implemented by manipulating the size of the array and accessing elements at specific indices.
Doubly Linked List: In this approach, you can use a doubly linked list to implement a stack. Each node in the linked list will represent an element in the stack, and the top of the stack will be represented by the tail of the linked list. The stack operations can be implemented by manipulating the tail pointer and adding/removing nodes at the end of the linked list.
Circular Array: Another approach is to use a circular array to implement a stack. In this approach, you can maintain a fixed-size array and two indices: one for the top of the stack and another for the next available position. The stack operations can be implemented by updating the indices and accessing elements at specific positions in the circular array.
These are just a few examples of how you can implement a stack using different data structures. The choice of implementation depends on factors such as the desired time complexity, space requirements, and specific application needs.

Here are several possible methods to implement a stack using different data structures:

Array-based implementation: Use a dynamic or fixed-size array to store the stack elements. The top of the stack is tracked using an index.
Linked list-based implementation: Use a singly linked list or a doubly linked list to represent the stack. Each node in the linked list holds a stack element, and the top of the stack is represented by the head or tail of the linked list.
Dynamic array-based implementation: Use a resizable array data structure, such as std::vector in C++, to implement the stack. The array can grow or shrink dynamically as elements are pushed or popped from the stack.
Circular array-based implementation: Use a fixed-size circular array to implement the stack. Maintain two indices: one for the top of the stack and another for the next available position. Elements are added and removed from the stack by updating the indices accordingly.
Dynamic linked list-based implementation: Use a dynamic linked list structure, where each node contains a stack element and a pointer to the next node. This allows for dynamic memory allocation and efficient addition/removal of elements.
Doubly linked list-based implementation: Use a doubly linked list to represent the stack, where each node has references to both the previous and next nodes. This allows for efficient addition/removal at both ends of the list.
Vector-based implementation: Use a vector data structure (e.g., std::vector in C++) to implement the stack. The vector provides dynamic resizing and efficient random access, making it suitable for stack operations.;
Deque-based implementation: Use a double-ended queue (deque) data structure, such as std::deque in C++, to implement the stack. Elements can be added or removed from either end of the deque, simulating stack behavior.

These are some of the commonly used methods to implement a stack using different data structures. Each approach has its own advantages and considerations, so the choice depends on factors such as performance requirements, memory usage, and programming language capabilities.

Here are some possible methods to implement a queue using different data structures:

Array-based implementation:
- Use an array to store the elements of the queue. Maintain two pointers, front and rear, to keep track of the start and end of the queue. When an element is enqueued, it is added to the rear of the queue, and when an element is dequeued, it is removed from the front of the queue. This implementation can be done using a fixed-size array or a dynamic array.
Linked list-based implementation:
- Use a singly linked list or a doubly linked list to store the elements of the queue. Maintain two pointers, front and rear, to keep track of the start and end of the queue. When an element is enqueued, it is added to the rear of the linked list, and when an element is dequeued, it is removed from the front of the linked list. This implementation allows for dynamic resizing of the queue.
Circular array-based implementation:
- Use a circular array to store the elements of the queue. Maintain two pointers, front and rear, to keep track of the start and end of the queue. When an element is enqueued, it is added to the rear of the circular array, taking care of wrapping around when the rear reaches the end of the array. When an element is dequeued, it is removed from the front of the circular array, again taking care of wrapping around when the front reaches the end of the array. This implementation allows efficient space utilization.
Doubly ended queue (Deque):
- Use a doubly linked list or a circular array to implement a deque. A deque supports insertion and deletion of elements from both ends, unlike a standard queue. This allows for operations like enqueueing and dequeueing from both ends of the deque, making it more versatile.
Two stacks implementation:
- Use two stacks to implement a queue. One stack is used for enqueue operations, and the other stack is used for dequeue operations. When an element is enqueued, it is pushed onto the enqueue stack. When an element is dequeued, if the dequeue stack is empty, all the elements from the enqueue stack are popped and pushed onto the dequeue stack, reversing their order. This ensures that the oldest element is at the top of the dequeue stack and can be popped to simulate a dequeue operation. This implementation provides a queue behavior using two stacks.

These are just a few examples of possible methods to implement a queue using different data structures. Each method has its own advantages and considerations, such as time complexity, space complexity, and flexibility. The choice of implementation depends on the specific requirements and constraints of the problem you are trying to solve.

Stack data structure can be used to solve various problems in software engineering. Here are a few examples of problems where stack can be utilized:

Parentheses Matching: Use a stack to check if the parentheses in a given expression are balanced or not. This problem is commonly used to validate the syntax of programming language constructs.
Function Call Stack: In programming languages, when a function is called, its execution context is pushed onto the stack, and when the function completes, its context is popped from the stack. The stack allows for proper function call and return order, maintaining the execution flow.
Expression Evaluation: Convert infix expressions (e.g., 2 + 3 * 4) to postfix or prefix notation using a stack, and then evaluate the resulting postfix or prefix expression. The stack helps in maintaining the order of operations and operands during evaluation.
Depth-First Search (DFS): Implement DFS using a stack to traverse graphs or trees in a depth-first manner. The stack is used to keep track of the nodes to be visited and the path taken during the traversal.
Undo/Redo Functionality: Implement undo and redo operations in an application by maintaining a stack of actions. Each action is pushed onto the stack when performed, and undoing an action involves popping it from the stack.
Backtracking Algorithms: Stack can be used in backtracking algorithms like the N-Queens problem or solving Sudoku puzzles. The stack stores the partial solutions or choices made, allowing for easy backtracking to explore different paths.
Browser History: Implementing a browser is back and forward functionality can be done using a stack. Each visited URL is pushed onto the stack, and going back involves popping the URL from the stack.

These are just a few examples, and there are many more problems where stack data structure can be effectively used. The key is to understand the Last-In-First-Out (LIFO) nature of stacks and identify scenarios where maintaining a LIFO order is beneficial for solving the problem efficiently.

Now, let's test our understanding of stacks and queues with some thought-provoking questions. Get ready to delve into the intricacies of LIFO and FIFO, and see how well we grasp these concepts. Let's begin!

🏆 Three in One

Three in One: Describe how you could use a single array to implement three stacks.

more details »

🏆 Stack Min

How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should all operate in 0(1) time.

more details »

🏆 Stack of Plates

Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetO-fStacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOfStacks. push() and SetOfStacks. pop() should behave identically to a single stack (that is, pop () should return the same values as it would if there were just a single stack). FOLLOW UP Implement a function popAt ( int index) which performs a pop operation on a specific sub-stack.

more details »

🏆 Queue via Stacks

Implement a MyQueue class which implements a queue using two stacks.

more details »

🏆 Sort Stack

Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and is Empty.

more details »

🏆 Animal Shelter

An animal shelter, which holds only dogs and cats, operates on a strictly"first in, first out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog, and dequeueCat. You may use the built-in Linked list data structure.

more details »