Implement Quack Data Structure with Three Stacks

Problem

A quack is a data structure combining properties of both stacks and queues. It can be viewed as a list of elements written left to right such that three operations are possible:

• push(x): add a new item x to the left end of the list
• pop(): remove and return the item on the left end of the list
• pull(): remove the item on the right end of the list.

Implement a quack using three stacks and O(1) additional memory, so that the amortized time for any push, pop, or pull operation is O(1).

Examples

Example 1

Input: push(1), push(2), push(3), pop()
Output: 3
Explanation: After pushes, quack is [3, 2, 1]. Pop removes leftmost element 3.

Example 2

Input: push(1), push(2), push(3), pull()
Output: 1
Explanation: After pushes, quack is [3, 2, 1]. Pull removes rightmost element 1.

Example 3

Input: push(1), push(2), pop(), push(3), pull(), push(4)
Output: Quack becomes [4, 3]
Explanation: [1] → [2,1] → [2] → [3,2] → [3] → [4,3]

Example 4

Input: push(1), push(2), push(3), pull(), pull(), pull()
Output: 3, 2, 1
Explanation: Pull operations remove from right: 1, then 2, then 3.

Solution

Method 1 - Three Stack Architecture with Load Balancing

Intuition

The key insight is to use three stacks strategically: a left stack for recent pushes, a right stack for elements that will be pulled, and a middle stack as a buffer for transfers. We maintain the invariant that elements are distributed across stacks such that left operations (push/pop) primarily use the left stack, while right operations (pull) use the right stack. When stacks become unbalanced, we redistribute elements to maintain amortized O(1) performance.

Approach

1. Stack Organization:

   • leftStack: Contains recently pushed elements (top = leftmost in quack)
   • rightStack: Contains elements ready for pulling (top = rightmost in quack)
   • middleStack: Temporary stack for element transfers and rebalancing

2. Push Operation: Always push to leftStack

3. Pop Operation:

   • If leftStack not empty, pop from it
   • Otherwise, redistribute elements and then pop

4. Pull Operation:

   • If rightStack not empty, pop from it
   • Otherwise, redistribute elements and then pop

5. Rebalancing Strategy: When a stack is empty and we need an element from it, transfer roughly half the elements from the other stack through the middle stack

Code

C++

class Solution {
    stack<int> leftStack, rightStack, middleStack;
    
public:
    void push(int x) {
        leftStack.push(x);
    }
    
    int pop() {
        if (leftStack.empty()) {
            rebalanceForPop();
        }
        
        int result = leftStack.top();
        leftStack.pop();
        return result;
    }
    
    int pull() {
        if (rightStack.empty()) {
            rebalanceForPull();
        }
        
        int result = rightStack.top();
        rightStack.pop();
        return result;
    }
    
private:
    void rebalanceForPop() {
        if (rightStack.empty()) return;
        
        // Move half of rightStack to leftStack via middleStack
        int size = rightStack.size();
        int toMove = size / 2;
        
        // First, move elements to middle stack (reverses order)
        for (int i = 0; i < toMove; i++) {
            middleStack.push(rightStack.top());
            rightStack.pop();
        }
        
        // Then move from middle to left (reverses back to correct order)
        while (!middleStack.empty()) {
            leftStack.push(middleStack.top());
            middleStack.pop();
        }
    }
    
    void rebalanceForPull() {
        if (leftStack.empty()) return;
        
        // Move half of leftStack to rightStack via middleStack
        int size = leftStack.size();
        int toMove = size / 2;
        
        // Move elements to middle stack
        for (int i = 0; i < toMove; i++) {
            middleStack.push(leftStack.top());
            leftStack.pop();
        }
        
        // Move from middle to right stack
        while (!middleStack.empty()) {
            rightStack.push(middleStack.top());
            middleStack.pop();
        }
    }
    
    bool empty() {
        return leftStack.empty() && rightStack.empty();
    }
};

Go

type Quack struct {
    leftStack   []int
    rightStack  []int
    middleStack []int
}

func NewQuack() *Quack {
    return &Quack{
        leftStack:   make([]int, 0),
        rightStack:  make([]int, 0),
        middleStack: make([]int, 0),
    }
}

func (q *Quack) Push(x int) {
    q.leftStack = append(q.leftStack, x)
}

func (q *Quack) Pop() int {
    if len(q.leftStack) == 0 {
        q.rebalanceForPop()
    }
    
    result := q.leftStack[len(q.leftStack)-1]
    q.leftStack = q.leftStack[:len(q.leftStack)-1]
    return result
}

func (q *Quack) Pull() int {
    if len(q.rightStack) == 0 {
        q.rebalanceForPull()
    }
    
    result := q.rightStack[len(q.rightStack)-1]
    q.rightStack = q.rightStack[:len(q.rightStack)-1]
    return result
}

func (q *Quack) rebalanceForPop() {
    if len(q.rightStack) == 0 {
        return
    }
    
    size := len(q.rightStack)
    toMove := size / 2
    
    // Move half to middle stack
    for i := 0; i < toMove; i++ {
        q.middleStack = append(q.middleStack, q.rightStack[len(q.rightStack)-1])
        q.rightStack = q.rightStack[:len(q.rightStack)-1]
    }
    
    // Move from middle to left
    for len(q.middleStack) > 0 {
        q.leftStack = append(q.leftStack, q.middleStack[len(q.middleStack)-1])
        q.middleStack = q.middleStack[:len(q.middleStack)-1]
    }
}

func (q *Quack) rebalanceForPull() {
    if len(q.leftStack) == 0 {
        return
    }
    
    size := len(q.leftStack)
    toMove := size / 2
    
    // Move half to middle stack
    for i := 0; i < toMove; i++ {
        q.middleStack = append(q.middleStack, q.leftStack[len(q.leftStack)-1])
        q.leftStack = q.leftStack[:len(q.leftStack)-1]
    }
    
    // Move from middle to right
    for len(q.middleStack) > 0 {
        q.rightStack = append(q.rightStack, q.middleStack[len(q.middleStack)-1])
        q.middleStack = q.middleStack[:len(q.middleStack)-1]
    }
}

func (q *Quack) IsEmpty() bool {
    return len(q.leftStack) == 0 && len(q.rightStack) == 0
}

Java

class Solution {
    private Stack<Integer> leftStack;
    private Stack<Integer> rightStack;
    private Stack<Integer> middleStack;
    
    public Solution() {
        leftStack = new Stack<>();
        rightStack = new Stack<>();
        middleStack = new Stack<>();
    }
    
    public void push(int x) {
        leftStack.push(x);
    }
    
    public int pop() {
        if (leftStack.isEmpty()) {
            rebalanceForPop();
        }
        return leftStack.pop();
    }
    
    public int pull() {
        if (rightStack.isEmpty()) {
            rebalanceForPull();
        }
        return rightStack.pop();
    }
    
    private void rebalanceForPop() {
        if (rightStack.isEmpty()) return;
        
        int size = rightStack.size();
        int toMove = size / 2;
        
        // Move elements to middle stack
        for (int i = 0; i < toMove; i++) {
            middleStack.push(rightStack.pop());
        }
        
        // Move from middle to left stack
        while (!middleStack.isEmpty()) {
            leftStack.push(middleStack.pop());
        }
    }
    
    private void rebalanceForPull() {
        if (leftStack.isEmpty()) return;
        
        int size = leftStack.size();
        int toMove = size / 2;
        
        // Move elements to middle stack
        for (int i = 0; i < toMove; i++) {
            middleStack.push(leftStack.pop());
        }
        
        // Move from middle to right stack
        while (!middleStack.isEmpty()) {
            rightStack.push(middleStack.pop());
        }
    }
    
    public boolean isEmpty() {
        return leftStack.isEmpty() && rightStack.isEmpty();
    }
}

Python

class Solution:
    def __init__(self):
        self.leftStack: List[int] = []
        self.rightStack: List[int] = []
        self.middleStack: List[int] = []
    
    def push(self, x: int) -> None:
        self.leftStack.append(x)
    
    def pop(self) -> int:
        if not self.leftStack:
            self._rebalanceForPop()
        return self.leftStack.pop()
    
    def pull(self) -> int:
        if not self.rightStack:
            self._rebalanceForPull()
        return self.rightStack.pop()
    
    def _rebalanceForPop(self) -> None:
        if not self.rightStack:
            return
        
        size = len(self.rightStack)
        toMove = size // 2
        
        # Move half to middle stack
        for _ in range(toMove):
            self.middleStack.append(self.rightStack.pop())
        
        # Move from middle to left stack
        while self.middleStack:
            self.leftStack.append(self.middleStack.pop())
    
    def _rebalanceForPull(self) -> None:
        if not self.leftStack:
            return
        
        size = len(self.leftStack)
        toMove = size // 2
        
        # Move half to middle stack
        for _ in range(toMove):
            self.middleStack.append(self.leftStack.pop())
        
        # Move from middle to right stack
        while self.middleStack:
            self.rightStack.append(self.middleStack.pop())
    
    def isEmpty(self) -> bool:
        return not self.leftStack and not self.rightStack

Complexity

• ⏰ Time complexity: O(1) amortized for all operations. While individual rebalancing operations can take O(n), each element is moved at most a constant number of times across its lifetime, making the amortized cost O(1).
• 🧺 Space complexity: O(n) where n is the number of elements in the quack, using three stacks. Additional space usage is O(1) as required.

Method 2 - Optimized Two-Stack Approach with Lazy Migration

Intuition

We can optimize the approach by using primarily two stacks (left and right) and only using the middle stack during transfers. This reduces memory overhead and simplifies the logic while maintaining the same amortized bounds. The key is to perform lazy migration - only move elements when absolutely necessary.

Approach

1. Primary Stacks: Use leftStack for push/pop operations and rightStack for pull operations
2. Lazy Migration: Only rebalance when the required stack is empty
3. Smart Rebalancing: Move approximately half the elements to balance future operations
4. Middle Stack Usage: Use middle stack only during the transfer process
5. Optimization: Clear middle stack immediately after transfer to minimize memory usage

Code

C++

class Solution {
    stack<int> left, right, temp;
    
public:
    void push(int x) {
        left.push(x);
    }
    
    int pop() {
        if (left.empty() && right.empty()) {
            throw runtime_error("Quack is empty");
        }
        
        if (left.empty()) {
            migrate(right, left);
        }
        
        int ans = left.top();
        left.pop();
        return ans;
    }
    
    int pull() {
        if (left.empty() && right.empty()) {
            throw runtime_error("Quack is empty");
        }
        
        if (right.empty()) {
            migrate(left, right);
        }
        
        int ans = right.top();
        right.pop();
        return ans;
    }
    
private:
    void migrate(stack<int>& from, stack<int>& to) {
        if (from.empty()) return;
        
        int totalSize = from.size();
        int keepInFrom = totalSize / 2;
        int moveToTo = totalSize - keepInFrom;
        
        // Move elements that will go to 'to' stack into temp
        for (int i = 0; i < moveToTo; i++) {
            temp.push(from.top());
            from.pop();
        }
        
        // Move from temp to destination stack
        while (!temp.empty()) {
            to.push(temp.top());
            temp.pop();
        }
    }
    
    bool empty() {
        return left.empty() && right.empty();
    }
};

Go

type OptimizedQuack struct {
    left  []int
    right []int
    temp  []int
}

func NewOptimizedQuack() *OptimizedQuack {
    return &OptimizedQuack{
        left:  make([]int, 0),
        right: make([]int, 0),
        temp:  make([]int, 0),
    }
}

func (q *OptimizedQuack) Push(x int) {
    q.left = append(q.left, x)
}

func (q *OptimizedQuack) Pop() int {
    if len(q.left) == 0 && len(q.right) == 0 {
        panic("Quack is empty")
    }
    
    if len(q.left) == 0 {
        q.migrate(&q.right, &q.left)
    }
    
    ans := q.left[len(q.left)-1]
    q.left = q.left[:len(q.left)-1]
    return ans
}

func (q *OptimizedQuack) Pull() int {
    if len(q.left) == 0 && len(q.right) == 0 {
        panic("Quack is empty")
    }
    
    if len(q.right) == 0 {
        q.migrate(&q.left, &q.right)
    }
    
    ans := q.right[len(q.right)-1]
    q.right = q.right[:len(q.right)-1]
    return ans
}

func (q *OptimizedQuack) migrate(from *[]int, to *[]int) {
    if len(*from) == 0 {
        return
    }
    
    totalSize := len(*from)
    keepInFrom := totalSize / 2
    moveToTo := totalSize - keepInFrom
    
    // Move elements to temp
    for i := 0; i < moveToTo; i++ {
        q.temp = append(q.temp, (*from)[len(*from)-1])
        *from = (*from)[:len(*from)-1]
    }
    
    // Move from temp to destination
    for len(q.temp) > 0 {
        *to = append(*to, q.temp[len(q.temp)-1])
        q.temp = q.temp[:len(q.temp)-1]
    }
}

func (q *OptimizedQuack) IsEmpty() bool {
    return len(q.left) == 0 && len(q.right) == 0
}

Java

class Solution {
    private Stack<Integer> left, right, temp;
    
    public Solution() {
        left = new Stack<>();
        right = new Stack<>();
        temp = new Stack<>();
    }
    
    public void push(int x) {
        left.push(x);
    }
    
    public int pop() {
        if (left.isEmpty() && right.isEmpty()) {
            throw new IllegalStateException("Quack is empty");
        }
        
        if (left.isEmpty()) {
            migrate(right, left);
        }
        
        return left.pop();
    }
    
    public int pull() {
        if (left.isEmpty() && right.isEmpty()) {
            throw new IllegalStateException("Quack is empty");
        }
        
        if (right.isEmpty()) {
            migrate(left, right);
        }
        
        return right.pop();
    }
    
    private void migrate(Stack<Integer> from, Stack<Integer> to) {
        if (from.isEmpty()) return;
        
        int totalSize = from.size();
        int keepInFrom = totalSize / 2;
        int moveToTo = totalSize - keepInFrom;
        
        // Move elements to temp stack
        for (int i = 0; i < moveToTo; i++) {
            temp.push(from.pop());
        }
        
        // Move from temp to destination
        while (!temp.isEmpty()) {
            to.push(temp.pop());
        }
    }
    
    public boolean isEmpty() {
        return left.isEmpty() && right.isEmpty();
    }
}

Python

class Solution:
    def __init__(self):
        self.left: List[int] = []
        self.right: List[int] = []
        self.temp: List[int] = []
    
    def push(self, x: int) -> None:
        self.left.append(x)
    
    def pop(self) -> int:
        if not self.left and not self.right:
            raise ValueError("Quack is empty")
        
        if not self.left:
            self._migrate(self.right, self.left)
        
        return self.left.pop()
    
    def pull(self) -> int:
        if not self.left and not self.right:
            raise ValueError("Quack is empty")
        
        if not self.right:
            self._migrate(self.left, self.right)
        
        return self.right.pop()
    
    def _migrate(self, from_stack: List[int], to_stack: List[int]) -> None:
        if not from_stack:
            return
        
        totalSize = len(from_stack)
        keepInFrom = totalSize // 2
        moveToTo = totalSize - keepInFrom
        
        # Move elements to temp
        for _ in range(moveToTo):
            self.temp.append(from_stack.pop())
        
        # Move from temp to destination
        while self.temp:
            to_stack.append(self.temp.pop())
    
    def isEmpty(self) -> bool:
        return not self.left and not self.right

Complexity

• ⏰ Time complexity: O(1) amortized. Each element is moved at most twice during its lifetime in the data structure, giving constant amortized cost per operation.
• 🧺 Space complexity: O(n) for storing n elements plus O(1) additional memory as specified in the problem requirements.